package sort;

public class QuickSort {

    public static void sort(int[] nums,int S, int E){
        if(S>=E)
            return;
        int start = S,end = E,temp = nums[start];
        while(start<end){
            //从后向前
            while(start<end&&nums[end]>=temp)
                end--;
            if(start<end)
                nums[start] = nums[end];
            //从前向后
            while (start<end&&nums[start]<=temp)
                start++;
            if(start<end)
                nums[end] = nums[start];
        }
        nums[start]=temp;
        sort(nums,S,end-1);
        sort(nums,end+1,E);
    }




}




/*
从数组中挑一个元素作为基准数，一般情况下我们选择第一个 nums[i]，保存为 standardNum，可以理解为 nums[i] 坑位的数被拎出来了，留下空的坑位。
取数组的左边界索引指针 i，右边界索引指针 j，j 从右边往左边，寻找到比 standardNum 小的数，停下来，写到 nums[i] 的坑位，nums[j] 的坑位空出来。 索引指针i 从左边往右边找，寻找比 standardNum 大的数，停下来，写到 nums[j] 的坑位，这个时候，num[i] 的坑位空出来（前提是 i 和 j 不相撞）。
上面的 i 和 j 循环步骤 2，直到两个索引指针 i 和 j 相撞，将基准值 standardNum 写到坑位 nums[i] 中，这时候，standardNum 左边的数都小于等于它本身，右边的数都大于等于它本身。
分别对 standardNum 左边的子数组和右边的子数组，循环执行前面的 1，2，3，直到不可再分，并且有序。
 */